package com.example.leetcode.string.common;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class StringUtils {

    /**
     * 交替合并字符串
     * <p>
     * 1 <= word1.length, word2.length <= 100
     * word1 和 word2 由小写英文字母组成
     *
     * @param word1
     * @param word2
     * @return
     */
    public static String mergeTwoStringsAlternately(String word1, String word2) {
        String result = "";
        // 两个都为空
        if (isBlank(word1) && isBlank(word2)) {
            return result;
        }
        // 1为空
        if (isBlank(word1)) {
            return result + word2;
        }
        // 2位空
        if (isBlank(word2)) {
            return result + word1;
        }
        // 两个都不为空
        int position = 0;
        int minLength = Math.min(word1.length(), word2.length());
        while (position < minLength) {
            result = result + word1.charAt(position);
            result = result + word2.charAt(position);
            position++;
        }
        if (position == word1.length() && position == word2.length()) {
            return result;
        } else if (position == word1.length()) {
            // 从索引为j的位置开始拼到最后
            return result + word2.substring(position);
        } else {
            return result + word1.substring(position);
        }
    }

    /**
     * 判断字符串是否为 null 空串 或者空格串
     *
     * @param word
     * @return
     */
    private static boolean isBlank(String word) {
        if (word == null) {
            return true;
        }
        if (word.length() == 0) {
            return true;
        }
        for (int i = 0; i < word.length(); i++) {
            if (!Character.isWhitespace(word.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    public static int minimumMoves(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] array = s.toCharArray();
        int i = 0;
        int result = 0;
        while (i < array.length) {
            if (array[i] == 'X') {
                array[i] = 'O';
                if (i + 1 < array.length && array[i + 1] == 'X') {
                    array[i + 1] = 'O';
                }
                if (i + 2 < array.length && array[i + 2] == 'X') {
                    array[i + 2] = 'O';
                }
                i = i + 3;
                result++;
            } else {
                i = i + 1;
            }
        }
        return result;
    }

    public static int minimumLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        char[] array = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {
            if (left == right) {
                return 1;
            }
            char first = array[left];
            char end = array[right];
            if (first != end) {
                break;
            }
            // 去除前缀
            while (left < right && array[left] == first) {
                left++;
            }
            // 当目前范围内所有字符为同一种时
            if (left == right) {
                return 0;
            }
            // 去除后缀
            while (left < right && array[right] == end) {
                right--;
            }
        }
        return right - left + 1;
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String result = getLongestCommonPrefixOfTwoString(strs[0], strs[1]);
        for (int i = 2; i < strs.length; i++) {
            result = getLongestCommonPrefixOfTwoString(result, strs[i]);
        }
        return result;
    }

    private static String getLongestCommonPrefixOfTwoString(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
            return "";
        }
        int minLength = str1.length() <= str2.length() ? str1.length() : str2.length();
        int i = 0;
        for (; i < minLength; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                break;
            }
        }
        return str1.substring(0, i);
    }

    public static char repeatedCharacter(String s) {
        boolean[] show = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!show[c - 'a']) {
                show[c - 'a'] = true;
            } else {
                return c;
            }
        }
        return '0';
    }

    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public static int lengthOfLastWord(String s) {
        int start = s.length() - 1;
        while (s.charAt(start) == ' ') {
            start--;
        }
        int end = start;
        while (end >= 0 && s.charAt(end) != ' ') {
            end--;
        }
        return start - end;
    }

    public static void reverseCharArray(char[] chars) {
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    public static boolean areNumbersAscending(String s) {
        int lastNum = 0;
        int curNum = 0;
        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            if (curChar == ' ' && curNum > 0) {
                if (curNum <= lastNum) {
                    return false;
                } else {
                    lastNum = curNum;
                    curNum = 0;
                }
            }
            if (curChar >= 'a' && curChar <= 'z') {
                continue;
            }
            if (curChar >= '0' && curChar <= '9') {
                curNum = curNum * 10 + Integer.parseInt(String.valueOf(curChar));
            }
        }
        return curNum <= 0 || curNum > lastNum;
    }

    public static boolean isPalindrome(String s) {
        s = s.toLowerCase();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !checkChar(s.charAt(left))) {
                left++;
            }
            while (left < right && !checkChar(s.charAt(right))) {
                right--;
            }
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    private static boolean checkChar(char c) {
        return c >= '0' && c <= '9' || c >= 'a' && c <= 'z';
    }

    public static int prefixCount(String[] words, String pref) {
        int result = 0;
        for (String s : words) {
            if (s.startsWith(pref)) {
                result++;
            }
        }
        return result;
    }

    public static boolean isIsomorphic(String s, String t) {
        return solveIsIsomorphic(s, t) && solveIsIsomorphic(t, s);
    }

    private static boolean solveIsIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            Character getResult = map.get(sc);
            if (getResult == null) {
                map.put(sc, tc);
            } else {
                if (getResult != tc) {
                    return false;
                }
            }
        }
        return true;
    }

    public static String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>();
        for (List<String> list : knowledge) {
            map.put(list.get(0), list.get(1));
        }
        StringBuilder result = new StringBuilder();
        StringBuilder content = new StringBuilder();
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                flag = true;
            } else if (c == ')') {
                String value = map.get(content.toString());
                if (value != null) {
                    result.append(value);
                } else {
                    result.append("?");
                }
                content = new StringBuilder();
                flag = false;
            } else {
                if (flag) {
                    content.append(c);
                } else {
                    result.append(c);
                }
            }
        }
        return result.toString();
    }

    public static int rearrangeCharacters(String s, String target) {
        if (s.length() < target.length()) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> tar = new HashMap<>();
        for (int i = 0; i < target.length(); i++) {
            tar.merge(target.charAt(i), 1, Integer::sum);
        }
        for (int i = 0; i < s.length(); i++) {
            map.merge(s.charAt(i), 1, Integer::sum);
        }
        int result = Integer.MAX_VALUE;
        for (Character c : tar.keySet()) {
            Integer num = map.get(c);
            if (num == null) {
                return 0;
            }
            result = Math.min(result, num / tar.get(c));
        }
        return result;
    }

    public static int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.merge(s.charAt(i), 1, Integer::sum);
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }

    public static char findTheDifference(String s, String t) {
        int[] map = new int[26];
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']--;
        }
        for (int i = 0; i < map.length; i++) {
            if (map[i] != 0) {
                return (char) (i + 97);
            }
        }
        return ' ';
    }

    public static boolean canConstruct(String ransomNote, String magazine) {
        int[] map = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            map[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            int index = ransomNote.charAt(i) - 'a';
            if (map[index] == 0) {
                return false;
            } else {
                map[index]--;
            }
        }
        return true;
    }

    public static boolean isSubsequence(String s, String t) {
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        int indexS = 0;
        int indexT = 0;
        while (indexT < ta.length && indexS < sa.length) {
            while (ta[indexT] != sa[indexS]) {
                indexT++;
                if (indexT == ta.length) {
                    return false;
                }
            }
            indexS++;
            indexT++;
        }
        return indexS == sa.length;
    }

    public static boolean areSentencesSimilar(String sentence1, String sentence2) {

        String[] words1 = sentence1.split(" ");
        String[] words2 = sentence2.split(" ");
        int i = 0, j = 0;
        while (i < words1.length && i < words2.length && words1[i].equals(words2[i])) {
            i++;
        }
        while (j < words1.length - i && j < words2.length - i && words1[words1.length - j - 1].equals(words2[words2.length - j - 1])) {
            j++;
        }
        return i + j == Math.min(words1.length, words2.length);

    }

    public static int countSegments(String s) {
        if (s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        while (left <= right && (chars[left] == ' ' || chars[right] == ' ')) {
            if (chars[left] == ' ') {
                left++;
            }
            if (chars[right] == ' ') {
                right--;
            }
        }
        if (left > right) {
            return 0;
        }
        int result = 0;
        for (int i = left + 1; i <= right; i++) {
            if (chars[i] == ' ' && chars[i - 1] != ' ') {
                result++;
            }
        }
        return result + 1;
    }

    public static int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.merge(s.charAt(i), 1, Integer::sum);
        }
        int flag = 0;
        int result = 0;
        for (Character c : map.keySet()) {
            result += map.get(c) / 2;
            if (flag == 0 && map.get(c) % 2 == 1) {
                flag = 1;
            }
        }
        return result * 2 + flag;
    }

    public static boolean strongPasswordCheckerII(String password) {
        if (password.length() < 8) {
            return false;
        }
        boolean smallC = false;
        boolean bigC = false;
        boolean num = false;
        boolean special = false;
        char[] array = password.toCharArray();
        IntStream stream = "!@#$%^&*()-+".chars();
        List<Character> s = stream.mapToObj(c -> (char) c).collect(Collectors.toList());
        for (int i = 0; i < array.length; i++) {
            if (i != 0 && array[i] == array[i - 1]) {
                return false;
            }
            if (array[i] >= '0' && array[i] <= '9') {
                num = true;
            }
            if (array[i] >= 'a' && array[i] <= 'z') {
                smallC = true;
            }
            if (array[i] >= 'A' && array[i] <= 'Z') {
                bigC = true;
            }
            if (s.contains(array[i])) {
                special = true;
            }
        }
        return smallC && bigC && num && special;
    }

    public static boolean detectCapitalUse(String word) {
        char[] array = word.toCharArray();
        boolean showLow = false;
        boolean showBig = false;
        if (Character.isLowerCase(array[0])) {
            showLow = true;
        }
        for (int i = 1; i < array.length; i++) {
            if (Character.isUpperCase(array[i]) && showLow) {
                return false;
            }
            if (Character.isLowerCase(array[i]) && showBig) {
                return false;
            }
            if (Character.isLowerCase(array[i])) {
                showLow = true;
            }
            if (Character.isUpperCase(array[i])) {
                showBig = true;
            }
        }
        return true;
    }

    public static String reverseStr(String s, int k) {
        StringBuilder result = new StringBuilder();
        if (s.length() <= k) {
            result.append(new StringBuilder(s).reverse());
            return result.toString();
        }
        while (true) {
            if (s.length() <= k) {
                result.append(new StringBuilder(s).reverse());
                return result.toString();
            }

            String prefix;
            prefix = s.substring(0, k);
            result.append(new StringBuilder(prefix).reverse());
            s = s.substring(k);

            if (s.length() <= k) {
                result.append(s);
                break;
            } else {
                prefix = s.substring(0, k);
                result.append(prefix);
                s = s.substring(k);
            }
        }
        return result.toString();
    }

    public static String reverseWords(String s) {
        String[] split = s.split(" ");
        for (int i = 0; i < split.length; i++) {
            split[i] = new StringBuilder(split[i]).reverse().toString();
        }
        return String.join(" ", split);
    }

    public static void reverseWords(char[] s) {
        int left = 0;
        int right = 0;
        while (left < s.length) {
            while (s[right] != ' ') {
                right++;
                if (right == s.length) {
                    break;
                }
            }
            reverseCharArray(s, left, right - 1);
            if (right < s.length) {
                right++;
            }
            left = right;
        }
        reverseCharArray(s, 0, s.length - 1);
    }

    private static void reverseCharArray(char[] s, int left, int right) {
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }

    public static String toLowerCase(String s) {
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            if (Character.isUpperCase(array[i])) {
                array[i] = Character.toLowerCase(array[i]);
            }
        }
        return new String(array);
    }

    public static char nextGreatestLetter(char[] letters, char target) {
        for (char letter : letters) {
            if (letter > target) {
                return letter;
            }
        }
        return letters[0];
    }

    public static String mostCommonWord(String paragraph, String[] banned) {
        char[] array = paragraph.toCharArray();
        // 此处应该使用正则表达式匹配替换或者匹配分隔,但是正则表达式不会写
        // !?',;.
        for (int i = 0; i < array.length; i++) {
            char c = array[i];
            if (c == '!' || c == '?' || c == '\'' || c == ',' || c == ';' || c == '.') {
                array[i] = ' ';
            }
        }
        // Bob hit a ball  the hit BALL flew far after it was hit  the
        paragraph = new String(array);
        paragraph = paragraph.trim();
        paragraph = paragraph.toLowerCase();
        String[] words = paragraph.split("\\s+");
        Set<String> set = new HashSet<>();
        Collections.addAll(set, banned);
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (set.contains(word)) {
                continue;
            }
            map.merge(word, 1, Integer::sum);
        }
        int maxTime = 0;
        String maxWord = "";
        for (String word : map.keySet()) {
            Integer time = map.getOrDefault(word, 0);
            if (time > maxTime) {
                maxTime = time;
                maxWord = word;
            }
        }
        return maxWord;
    }

    public static int[] shortestToChar(String s, char c) {
        char[] charArray = s.toCharArray();
        List<Integer> posList = new ArrayList<>();
        int[] result = new int[charArray.length];
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == c) {
                result[i] = 0;
                posList.add(i);
            }
        }
        Integer firstPos = posList.get(0);
        for (int i = 0; i < firstPos; i++) {
            result[i] = firstPos - i;
        }
        Integer endPos = posList.get(posList.size() - 1);
        for (int i = endPos + 1; i < result.length; i++) {
            result[i] = i - endPos;
        }
        if (posList.size() == 1) {
            return result;
        }
        int area = 0;
        while (area + 1 < posList.size()) {
            int left = posList.get(area);
            int right = posList.get(area + 1);
            for (int i = left + 1; i < right; i++) {
                result[i] = Math.min(Math.abs(i - left), Math.abs(right - i));
            }
            area++;
        }
        return result;
    }

    public static String[] uncommonFromSentences(String s1, String s2) {
        Map<String, Integer> map = new HashMap<>();
        String[] words1 = s1.split(" ");
        String[] words2 = s2.split(" ");
        for (String s : words1) {
            map.merge(s, 1, Integer::sum);
        }
        for (String s : words2) {
            map.merge(s, 1, Integer::sum);
        }
        List<String> list = new ArrayList<>();
        for (String word : map.keySet()) {
            if (map.getOrDefault(word, 0) == 1) {
                list.add(word);
            }
        }
        String[] result = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public static String reverseWords2(String s) {
        s = s.trim();
        String[] split = s.split("\\s+");
        List<String> result = new ArrayList<>();
        for (int i = split.length - 1; i >= 0; i--) {
            result.add(split[i]);
        }
        return String.join(" ", result);
    }

    public static String reverseOnlyLetters(String s) {
        int left = 0;
        int right = s.length() - 1;
        char[] toCharArray = s.toCharArray();
        while (left < right) {
            while (left < right && !Character.isAlphabetic(toCharArray[left])) {
                left++;
            }
            while (left < right && !Character.isAlphabetic(toCharArray[right])) {
                right--;
            }
            char temp = toCharArray[left];
            toCharArray[left] = toCharArray[right];
            toCharArray[right] = temp;
            left++;
            right--;
        }
        return String.valueOf(toCharArray);
    }

    public static boolean canPermutePalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] array = s.toCharArray();
        for (char value : array) {
            map.merge(value, 1, Integer::sum);
        }
        boolean flag = false;
        for (Character c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                if (flag) {
                    return false;
                } else {
                    flag = true;
                }
            }
        }
        return true;
    }

    public static List<String> generatePalindromes(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] array = s.toCharArray();
        for (char value : array) {
            map.merge(value, 1, Integer::sum);
        }
        boolean flag = false;
        Character character = null;
        for (Character c : map.keySet()) {
            if (map.get(c) % 2 == 1) {
                if (flag) {
                    return Collections.emptyList();
                } else {
                    flag = true;
                    character = c;
                }
            }
        }
        List<String> result = new ArrayList<>();
        char[] curStr = new char[array.length];
        int left = 0;
        int right = curStr.length - 1;
        solveGeneratePalindromes(result, curStr, left, right, map, character);
        return result;
    }

    private static void solveGeneratePalindromes(List<String> result, char[] curStr, int left, int right, Map<Character, Integer> map, Character character) {
        if (left > right) {
            result.add(String.valueOf(curStr));
            return;
        }
        if (left == right) {
            if (character != null) {
                curStr[left] = character;
                result.add(String.valueOf(curStr));
            }
            return;
        }
        for (Character c : map.keySet()) {
            if (map.get(c) < 2) {
                continue;
            }
            curStr[left] = c;
            curStr[right] = c;
            map.merge(c, -2, Integer::sum);
            solveGeneratePalindromes(result, curStr, left + 1, right - 1, map, character);
            curStr[left] = ' ';
            curStr[right] = ' ';
            map.merge(c, 2, Integer::sum);
        }
    }

    public static int shortestDistance(String[] wordsDict, String word1, String word2) {
        int beforePos1 = -1;
        int beforePos2 = -1;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < wordsDict.length; i++) {
            String word = wordsDict[i];
            if (word.equals(word1)) {
                beforePos1 = i;
                if (beforePos2 >= 0) {
                    result = Math.min(result, i - beforePos2);
                }
            }
            if (word.equals(word2)) {
                beforePos2 = i;
                if (beforePos1 >= 0) {
                    result = Math.min(result, i - beforePos1);
                }
            }
        }
        return result;
    }

    public static int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        int result = Integer.MAX_VALUE;
        if (!word1.equals(word2)) {
            return shortestDistance(wordsDict, word1, word2);
        } else {
            int beforeIndex = -1;
            for (int i = 0; i < wordsDict.length; i++) {
                if (wordsDict[i].equals(word1)) {
                    if (beforeIndex >= 0) {
                        result = Math.min(result, i - beforeIndex);
                    }
                    beforeIndex = i;
                }
            }
        }
        return result;
    }

    public static String digitSum(String s, int k) {
        String result = "";
        while (s.length() > k) {


        }


        return s;
    }

    public static String greatestLetter(String s) {
        if (s.length() == 0) {
            return "result";
        }
        boolean[] small = new boolean[26];
        boolean[] big = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isUpperCase(c)) {
                big[c - 'A'] = true;
            } else {
                small[c - 'a'] = true;
            }
        }
        for (int i = 25; i >= 0; i--) {
            if (big[i] && small[i]) {
                return String.valueOf((char) (i + 65));
            }
        }
        return "";
    }

    public static int countAsterisks(String s) {
        boolean valid = true;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '|') {
                valid = !valid;
            } else if (c == '*' && valid) {
                res++;
            }
        }
        return res;
    }

    public static int balancedString(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            cnt[idx(c)]++;
        }

        int partial = s.length() / 4;
        int res = s.length();

        if (check(cnt, partial)) {
            return 0;
        }
        for (int l = 0, r = 0; l < s.length(); l++) {
            while (r < s.length() && !check(cnt, partial)) {
                cnt[idx(s.charAt(r))]--;
                r++;
            }
            if (!check(cnt, partial)) {
                break;
            }
            res = Math.min(res, r - l);
            cnt[idx(s.charAt(l))]++;
        }
        return res;
    }

    public static int idx(char c) {
        return c - 'A';
    }

    public static boolean check(int[] cnt, int partial) {
        return cnt[idx('Q')] <= partial && cnt[idx('W')] <= partial && cnt[idx('E')] <= partial && cnt[idx('R')] <= partial;
    }

    public static String convert(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        int c = (n + t - 1) / t * (r - 1);
        char[][] mat = new char[r][c];
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s.charAt(i);
            if (i % t < r - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        StringBuffer ans = new StringBuffer();
        for (char[] row : mat) {
            for (char ch : row) {
                if (ch != 0) {
                    ans.append(ch);
                }
            }
        }
        return ans.toString();

    }

    public static String convertPro(String s, int numRows) {
        String[] strings = new String[numRows];
        Arrays.fill(strings, "");
        int index = 0;
        int dir = 1;
        for (int i = 0; i < s.length(); i++) {
            strings[index % numRows] += s.charAt(i);
            if (index == 0) {
                dir = 1;
            } else if (index == numRows - 1) {
                dir = -1;
            }
            index = index + dir;
        }
        StringBuilder result = new StringBuilder();
        for (String string : strings) {
            result.append(string);
        }
        return result.toString();
    }

    public static int minimumSwap(String s1, String s2) {
        int xy = 0, yx = 0;
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            char a = s1.charAt(i), b = s2.charAt(i);
            if (a == 'x' && b == 'y') {
                xy++;
            }
            if (a == 'y' && b == 'x') {
                yx++;
            }
        }
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }

    public static int maxScoreWords(String[] words, char[] letters, int[] score) {
        int n = words.length, res = 0;
        int[] count = new int[26];
        for (char c : letters) {
            count[c - 'a']++;
        }
        for (int s = 1; s < (1 << n); s++) {
            int[] wordCount = new int[26]; // 统计子集 s 所有单词的字母数目
            for (int k = 0; k < n; k++) {
                if ((s & (1 << k)) == 0) { // words[k] 不在子集 s 中
                    continue;
                }
                for (int i = 0; i < words[k].length(); i++) {
                    char c = words[k].charAt(i);
                    wordCount[c - 'a']++;
                }
            }
            boolean ok = true; // 判断子集 s 是否合法
            int sum = 0; // 保存子集 s 的得分
            for (int i = 0; i < 26; i++) {
                sum += score[i] * wordCount[i];
                ok = ok && (wordCount[i] <= count[i]);
            }
            if (ok) {
                res = Math.max(res, sum);
            }
        }
        return res;
    }

    public static boolean checkDistances(String s, int[] distance) {
        int[] actualDistance = new int[26];
        Arrays.fill(actualDistance, -1);
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            int pos = actualDistance[(int) array[i] - 97];
            if (pos == -1) {
                actualDistance[(int) array[i] - 97] = i;
            } else {
                if (i - pos - 1 != distance[(int) array[i] - 97]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean validWordAbbreviation(String word, String abbr) {
        char[] abbrArray = abbr.toCharArray();
        for (int i = 0; i < abbrArray.length; i++) {


        }


        return false;


    }

    public static int addMinimum(String word) {
        char[] array = word.toCharArray();
        int n = array.length;
        int ans = 0;
        // 处理头部
        if (array[0] == 'b') {
            ans += 1;
        } else if (array[0] == 'c') {
            ans += 2;
        }
        for (int i = 0; i < n; i++) {
            if (array[i] == 'a') {
                if (i + 1 >= n) {
                    ans += 2;
                } else if (array[i + 1] == 'a') {
                    ans += 2;
                } else if (array[i + 1] == 'c') {
                    ans += 1;
                }
            } else if (array[i] == 'b') {
                if (i + 1 >= n) {
                    ans += 1;
                } else if (array[i + 1] == 'a') {
                    ans += 1;
                } else if (array[i + 1] == 'b') {
                    ans += 2;
                }
            } else if (array[i] == 'c') {
                // 此处写上 i + 1 的判断是为了避免进入其他分支导致数组溢出
                if (i + 1 >= n) {
                    ans += 0;
                } else if (array[i + 1] == 'c') {
                    ans += 2;
                } else if (array[i + 1] == 'b') {
                    ans += 1;
                }
            }

        }
        return ans;
    }

    public static String lastSubstring(String s) {
        int left = 0;
        int right = 1;
        int k = 0;
        char[] str = s.toCharArray();
        while (right + k < s.length()) {
            if (str[left + k] == str[right + k]) {
                k++;
            } else if (str[left + k] < str[right + k]) {
                left = left + k + 1;
                k = 0;
                if (left >= right) {
                    right = left + 1;
                }
            } else {
                right = right + k + 1;
                k = 0;
            }
        }
        return s.substring(left);
    }

    public static boolean isUnique(String astr) {
        Map<Character, Boolean> map = new HashMap<>();
        for (int i = 0; i < astr.length(); i++) {
            if (!map.getOrDefault(astr.charAt(i), false)) {
                map.put(astr.charAt(i), true);
            } else {
                return false;
            }

        }
        return true;
    }

    public static String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }

    public static String reverseLeftWords(String s, int n) {
        n = n % (s.length());
        String ans = "";
        ans = s.substring(n) + s.substring(0, n);
        return ans;
    }

    public static boolean isNumber(String s) {
        s = s.trim();
        if (s.length() == 0) {
            return false;
        }
        int index = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'e' || s.charAt(i) == 'E') {
                index = i;
                break;
            }
        }
        String[] split = new String[2];
        if (index != -1) {
            split[0] = s.substring(0, index);
            split[1] = s.substring(index + 1);
        } else {
            split[0] = s;
            split[1] = "";
        }
        if (split[1].length() == 0 && index == -1) {
            return isDecimal(split[0]) || isInteger(split[0]);
        } else {
            return (isDecimal(split[0]) || isInteger(split[0])) && isInteger(split[1]);
        }
    }

    private static boolean isDecimal(String s) {
        if (!s.contains(".")) {
            return false;
        }
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '.') {
                index = i;
                break;
            }
        }
        String[] split = new String[2];
        split[0] = s.substring(0, index);
        split[1] = s.substring(index + 1);
        if (split[0].length() == 0 && split[1].length() == 0) {
            return false;
        }
        for (int m = 0; m < split.length; m++) {
            for (int i = 0; i < split[m].length(); i++) {
                char c = split[m].charAt(i);
                if (m == 0 && i == 0 && (c == '+' || c == '-')
                    && (split[m].length() > 1 || split[m + 1].length() > 0)) {
                    continue;
                }
                if (c >= '0' && c <= '9') {
                    continue;
                }
                return false;
            }
        }
        return true;
    }

    private static boolean isInteger(String s) {
        if (s.length() == 0 || s.contains(".")) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (i == 0 && (c == '+' || c == '-') && s.length() > 1) {
                continue;
            }
            if (c >= '0' && c <= '9') {
                continue;
            }
            return false;
        }
        return true;
    }

    public static boolean equalFrequency(String word) {
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < word.length(); i++) {
            freq.merge(word.charAt(i), 1, Integer::sum);
        }
        for (Character c : freq.keySet()) {
            // 尝试删掉一个字符
            freq.merge(c, -1, Integer::sum);
            Set<Integer> set = new HashSet<>(freq.values());
            set.remove(0);
            // 判断剩余字符的频率是否相同
            if (set.size() == 1) {
                return true;
            }
            // 恢复字符
            freq.merge(c, 1, Integer::sum);
        }
        return false;
    }

    public static boolean isOneEditDistance(String s, String t) {
        if (s.equals(t)) {
            return false;
        }
        if (s.length() == 0) {
            return t.length() == 1;
        }
        if (t.length() == 0) {
            return s.length() == 1;
        }
        if (s.length() == t.length()) {
            boolean diff = false;
            // 考虑字符替换
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != t.charAt(i)) {
                    if (!diff) {
                        diff = true;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        } else if (Math.abs(s.length() - t.length()) == 1) {
            int n = Math.min(s.length(), t.length());
            // 考虑字符插入或者删除
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) != t.charAt(i)) {
                    if (s.length() > t.length()) {
                        s = s.substring(0, i) + s.substring(i + 1);
                    } else {
                        t = t.substring(0, i) + t.substring(i + 1);
                    }
                    return s.equals(t);
                }
            }
            return true;
        } else {
            return false;
        }
    }

    public static int shortestWay(String source, String target) {


        return 0;
    }

    public static boolean isValid(String s) {
        while (s.contains("abc")) {
            s = s.replaceAll("abc", "");
        }
        return s.length() == 0;
    }

    /**
     * 将二维数组转为list集合
     *
     * @param strs
     * @return
     */
    public static List<List<String>> convertArrayToList(String[][] strs) {
        List<List<String>> ans = new ArrayList<>();
        for (String[] str : strs) {
            List<String> list = new ArrayList<>();
            Collections.addAll(list, str);
            ans.add(list);
        }
        return ans;
    }

    public static int countSeniors(String[] details) {
        int ans = 0;
        for (String detail : details) {
            int age = Integer.parseInt(detail.substring(11, 13));
            if (age > 60) {
                ans++;
            }
        }
        return ans;
    }

    public static long minimumCost(String s) {
        char[] array = s.toCharArray();
        long[] res = new long[]{0};
        while (true) {
            boolean op = reverse(array, res);
            if (!op) {
                break;
            }
        }
        return res[0];
    }

    private static boolean reverse(char[] array, long[] res) {
        boolean op = false;
        int index = -1;
        int index2 = -1;
        for (int i = 1; i < array.length - 1; i++) {
            if (array[i - 1] != array[i] && array[i + 1] != array[i]) {
                index = i;
                break;
            }
            if (!(array[i] == array[i - 1] && array[i] == array[i + 1])) {
                index2 = i;
            }
        }
        if (index != -1) {
            if (index + 1 <= array.length - 1 - index + 1) {
                for (int i = 0; i <= index; i++) {
                    reverseOne(array, i);
                    res[0]++;
                    op = true;
                }
            } else {
                for (int i = index; i < array.length; i++) {
                    reverseOne(array, i);
                    res[0]++;
                    op = true;
                }
            }
        } else {
            if (array[0] != array[1]) {
                reverseOne(array, 0);
                res[0]++;
                op = true;
            } else if (array[array.length - 1] != array[array.length - 1 - 1]) {
                reverseOne(array, array.length - 1);
                res[0]++;
                op = true;
            }
        }
        return op;
    }

    private static void reverseOne(char[] array, int i) {
        if (array[i] == '1') {
            array[i] = '0';
        } else {
            array[i] = '1';
        }
    }

    public static boolean repeatedSubstringPattern(String s) {
        // 拼接字符串并去掉头尾字符
        String combined = (s + s).substring(1, 2 * s.length() - 1);
        // 检查原字符串是否在新的字符串中
        return combined.contains(s);
    }

//    /**
//     * 使用栈来完成
//     * @param s
//     * @return
//     */
//    public static int longestValidParentheses(String s) {
//        int maxLen = 0;
//        Stack<Integer> stack = new Stack<>();
//        // 初始基准
//        stack.push(-1);
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) == '(') {
//                stack.push(i);
//            } else {
//                stack.pop();
//                if (stack.isEmpty()) {
//                    // 更新基准
//                    stack.push(i);
//                } else {
//                    maxLen = Math.max(maxLen, i - stack.peek());
//                }
//            }
//        }
//        return maxLen;
//    }

//    public int longestValidParentheses(String s) {
//        int maxLen = 0;
//        Deque<Integer> stack = new ArrayDeque<>();
//        stack.push(-1); // 初始基准点
//
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (c == '(') {
//                stack.push(i); // 左括号索引入栈
//            } else {
//                stack.pop(); // 匹配一个左括号
//                if (stack.isEmpty()) {
//                    stack.push(i); // 没有匹配的左括号，更新基准点
//                } else {
//                    int len = i - stack.peek(); // 当前有效长度
//                    maxLen = Math.max(maxLen, len);
//                }
//            }
//        }
//        return maxLen;
//    }

//
//    /**
//     * 使用双向计数
//     * @param s
//     * @return
//     */
//    public static int longestValidParentheses(String s) {
//        int maxLen = 0;
//        int left = 0;
//        int right = 0;
//
//        // 从左往右遍历
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) == '(') {
//                left++;
//            } else {
//                right++;
//            }
//            if (left == right) {
//                maxLen = Math.max(maxLen, right * 2);
//            } else if (right > left) {
//                // 往右遍历时，尝试根据左括号匹配右括号，当右括号更多时，一定会无法形成更长的有效括号，需要重置
//                left = 0;
//                right = 0;
//            }
//        }
//
//        // 从右往左遍历
//        for (int i = s.length() - 1; i >= 0; i--) {
//            if (s.charAt(i) == '(') {
//                left++;
//            } else {
//                right++;
//            }
//            if (left == right) {
//                maxLen = Math.max(maxLen, right * 2);
//            } else if (left > right) {
//                // 往左遍历应该是先有右括号，再尝试找左括号，因此当左括号更多时，是一定不能形成有效括号的，直接重置
//                left = 0;
//                right = 0;
//            }
//        }
//        return maxLen;
//    }

    public static int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 与前一个字符形成一对
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 与左侧的一个字符形成一对
                    dp[i] = dp[i - 1] + 2 +
                        ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }


    enum State {
        STATE_INITIAL,
        STATE_INT_SIGN,
        STATE_INTEGER,
        STATE_POINT,
        STATE_POINT_WITHOUT_INT,
        STATE_FRACTION,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END
    }

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_SPACE,
        CHAR_ILLEGAL
    }

    /**
     * 确定有限状态自动机
     * 其实本质上也是一种枚举，枚举了所有的可以被接受的规则
     *
     * @param s
     * @return
     */
    public static boolean isNumber2(String s) {
        Map<State, Map<CharType, State>> transfer = new HashMap<>();

        // 定义初始状态下对应的转移规则
        Map<CharType, State> initialMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_SPACE, State.STATE_INITIAL);
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
        }};
        transfer.put(State.STATE_INITIAL, initialMap);

        // 整数部分符号位
        Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
        }};
        transfer.put(State.STATE_INT_SIGN, intSignMap);

        // 整数
        Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_POINT, State.STATE_POINT);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_INTEGER, integerMap);

        // 左侧带整数的小数点
        Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_POINT, pointMap);

        // 左侧不带整数的小数点
        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
            // 只能接受数字类型的字符转移到小数状态
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
        }};
        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);

        // 小数
        Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_FRACTION, fractionMap);

        // 指数符号
        Map<CharType, State> expMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
        }};
        transfer.put(State.STATE_EXP, expMap);

        // 指数部分符号位
        Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
        }};
        transfer.put(State.STATE_EXP_SIGN, expSignMap);

        // 指数的数字部分
        Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_EXP_NUMBER, expNumberMap);

        // 末尾空格
        Map<CharType, State> endMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_SPACE, State.STATE_END);
        }};
        transfer.put(State.STATE_END, endMap);

        int length = s.length();
        // 指定当前状态是初始状态
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            // 当前状态
            CharType type = toCharType(s.charAt(i));
            // 如果当前状态下，转换规则中针对当前字符不存在对应的转换规则，则无法转移到下一个状态，判定该字符串不「被接受」
            if (!transfer.get(state).containsKey(type)) {
                return false;
            } else {
                // 根据当前字符类型转换到下一个状态
                state = transfer.get(state).get(type);
            }
        }
        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
    }

    public static CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return CharType.CHAR_NUMBER;
        } else if (ch == 'e' || ch == 'E') {
            return CharType.CHAR_EXP;
        } else if (ch == '.') {
            return CharType.CHAR_POINT;
        } else if (ch == '+' || ch == '-') {
            return CharType.CHAR_SIGN;
        } else if (ch == ' ') {
            return CharType.CHAR_SPACE;
        } else {
            return CharType.CHAR_ILLEGAL;
        }
    }

    public static String stringShift(String s, int[][] shift) {
        int left = 0;
        int right = 0;
        for (int[] ints : shift) {
            if (ints[0] == 0) {
                left += ints[1];
            } else {
                right += ints[1];
            }
        }
        String ans = "";
        int move = Math.abs(left - right) % s.length();
        if (left == right) {
            return s;
        } else if (right > left) {
            // 将右移转换为左移
            move = s.length() - move;
        }
        // 默认左移
        ans = s.substring(move) + s.substring(0, move);
        return ans;
    }

}
